P3960 [NOIP2017 提高组] 列队

发表于 更新于 分类于 ， ， 阅读次数： 作者 Pomelorin

题意

《\(900\) 亿 人 一 起 军 训》

Pomelorin 所在的方阵中有 \(n \times m\) 名学生（\(n\) 行 \(m\) 列）。初始时，第 \(i\) 行第 \(j\) 列 的学生的编号是 \((i-1)\times m + j\)。

一共发生了 \(q\) 件离队事件。每一次离队事件可以用数对 \((x,y)\)（满足 \(1 \le x \le n\)，\(1 \le y \le m\)）描述，表示第 \(x\) 行第 \(y\) 列的学生离队。在有学生离队后，队伍中出现了一个空位。之后方阵开始：

  • 向左看齐。这时第一列保持不动，所有学生向左填补空缺。之后空位在第 \(x\) 行第 \(m\) 列。

  • 向前看齐。这时第一行保持不动，所有学生向前填补空缺。之后空位在第 \(n\) 行第 \(m\) 列。

不能有两个或更多学生同时离队。离队的学生会自然地填补到第 \(n\) 行第 \(m\) 列。

计算每一次离队事件中，离队的同学的编号是多少。每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

数据规模与约定

测试点编号 \(n\) \(m\) \(q\) 其他约定
\(1\sim 6\) \(\le 10^3\) \(\le 10^3\) \(\le 500\) 无
\(7\sim 10\) \(\le 5\times 10^4\) \(\le 5\times 10^4\) \(\le 500\) 无
\(11\sim 12\) \(=1\) \(\le 10^5\) \(\le 10^5\) 所有事件 \(x=1\)
\(13\sim 14\) \(=1\) \(\le 3\times 10^5\) \(\le 3\times 10^5\) 所有事件 \(x=1\)
\(15\sim 16\) \(\le 3\times 10^5\) \(\le 3\times 10^5\) \(\le 3\times 10^5\) 所有事件 \(x=1\)
\(17\sim 18\) \(\le 10^5\) \(\le 10^5\) \(\le 10^5\) 无
\(19\sim 20\) \(\le 3\times 10^5\) \(\le 3\times 10^5\) \(\le 3\times 10^5\) 无

数据保证每一个事件满足 \(1 \le x \le n\)，\(1 \le y \le m\)。

点击查看题解

题解

1-6 模拟

直接按照题意模拟。时间复杂度：\(O(nm)\)。可以获得 \(30\) 分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve1()
{
	long long x,y;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=m;j++)
			g[i][j]=i*m-m+j;
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",g[x][y]);
		for(long long j=y;j<=m-1;j++) swap(g[x][j],g[x][j+1]);
		for(long long j=x;j<=n-1;j++) swap(g[j][m],g[j+1][m]);
	}
}

7-10 离散化

我们发现，虽然 \(n\) 和 \(m\) 的范围很大，但 \(q\) 很小；换言之，这个方阵中大部分行都用不到。所以我们对行进行离散。由于除了最后一列，其它列对方阵变换没有实质性影响；换言之，如果采用模拟的方式，其他列是不参与模拟过程的，所以我们只保留最后一列即可。

经过离散化，形成如下结构（有图片，显得这篇题解完整）：

然后直接按照题意模拟即可。

一个错误的离散化方法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve2()//错误做法 
{
	//离散化后结构：网格形 
	long long px=0,py=0;//离散化之后的矩阵的 m n 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",x+i,y+i);//Query 
		bx[i]=x[i];by[i]=y[i];//b 数组作为 tmp 
	}
	sort(bx+1,bx+1+q);sort(by+1,by+1+q);//Begin of 离散化 
	for(long long i=1;i<=q;i++)
	{
		if(bx[i-1]!=bx[i]) px++;
		if(by[i-1]!=by[i]) py++;
		fx[bx[i]]=px;fy[by[i]]=py;//f 数组用来根据原数找到相对位置 
		ax[px]=bx[i];ay[py]=by[i];//a 数组用来根据相对位置还原原数 
	}
	if(ay[py]!=m) by[++py]=m,fy[m]=py,ay[py]=m; 
	//End of 离散化 
	for(long long i=1;i<=px;i++)
		for(long long j=1;j<=py;j++)
			g[i][j]=ax[i]*m-m+ay[j];//g 数组下标是相对位置 
	for(long long i=1;i<=q;i++)
	{
		printf("%lld\n",g[fx[x[i]]][fy[y[i]]]);
		for(long long j=fy[y[i]];j<=py-1;j++) swap(g[fx[x[i]]][j],g[fx[x[i]]][j+1]);
		for(long long j=fx[x[i]];j<=px-1;j++) swap(g[j][py],g[j+1][py]);
	}
}

错误原因：把列也离散化，其实只保留最后一列即可；将每行破坏，不能得出正确答案。

在行离散过程中，将最后一列破坏，不能得出正确答案。

一个繁琐的离散化方法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve3()
{
	long long px=0;//离散化之后的行数 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",x+i,y+i);//Query 
		bx[i]=x[i];//b 数组作为 tmp 
	}
	sort(bx+1,bx+1+q);//Begin of 离散化 
	for(long long i=1;i<=q;i++)
	{
		if(bx[i-1]!=bx[i]) px++;
		fx[bx[i]]=px;//f 数组用来根据原数找到相对位置 
		ax[px]=bx[i];//a 数组用来根据相对位置还原原数 
	}
	for(long long i=1;i<=px;i++)
		for(long long j=1;j<=m-1;j++)
			G[i][j]=ax[i]*m-m+j;//G 数组下标是相对位置 
	for(long long i=1;i<=n;i++) L[i]=i*m;//L 数组是最后一列 
	for(long long i=1;i<=q;i++)
	{
		if(y[i]!=m) printf("%lld\n",G[fx[x[i]]][y[i]]);
		else printf("%lld\n",L[x[i]]);
		for(long long j=y[i];j<=m-2;j++) swap(G[fx[x[i]]][j],G[fx[x[i]]][j+1]);
		swap(G[fx[x[i]]][m-1],L[x[i]]);
		for(long long j=x[i];j<=n-1;j++) swap(L[j],L[j+1]);
	}
}

另外，我们考虑到，行与行直接不会互相影响。所以，我们不用考虑离散化后各行在数组中的位置。由此，可以得到下面的优化版代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve5()//对 solve3 的优化 行与行之间互不影响 
{
	long long px=0,x,y;
	for(long long i=1;i<=n;i++) L[i]=i*m; 
	for(long long i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		if(bx[x]==0) 
		{
			px++;bx[x]=px,h[px]=x;
			for(long long j=1;j<=m;j++)
				G[px][j]=x*m-m+j;
		}
		if(y!=m) printf("%lld\n",G[bx[x]][y]);
		else printf("%lld\n",L[x]);
		for(long long j=y;j<=m-2;j++) swap(G[bx[x]][j],G[bx[x]][j+1]);
		swap(G[bx[x]][m-1],L[x]);
		for(long long j=x;j<=n-1;j++) swap(L[j],L[j+1]);
	}
}

时间复杂度是 \(O(qm)\)，结合算法 1 可以得到 \(50\) 分。

11-16 树状数组 + 二分

注意到此时的数据范围，对于所有询问，\(x=1\)。也就是说，只有第一行和最后一列有用（11-14 数据点本质上和 15-16 一样，故划归到 11-16）。

此时，我们可以将弯折的序列“掰直”，用一个数组维护。即，把第一行和最后一列压成一维数组。

1
2
3
---
  |   =>   ----- (1,2,3,6,9)
  |

也就是说，维护的数列要支持两个操作：

  • 查询第 \(x\) 个元素。
  • 将元素移到数列最后面。

这里使用一个巧妙的方法：开一个标记数组，初始时 \(1\sim n+m-1\)（末尾）都为 \(1\)，表示这个位置上有数；在发生离队事件后，相应的位置变为 \(0\)，而当前数组末尾的下一个标记变为 \(1\)，表示这个数移到末尾。

对这个数组求前缀和，其前缀和数组中的值正对应查询中的 \(y\)（\(y\) 意义同题意所述），下标正对应现数列中第 \(y\) 个数所在位置。

树状数组维护标记数组的前缀和；利用二分，根据标记数组前缀和，来寻找数列中第 \(y\) 个数所在位置。

时间复杂度是 \(O(N(\log N)^2)\)，结合前面的算法可得到 \(80\) 分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve4()
{
	long long l,r,mid,Y,pos;
	for(long long i=1;i<=m;i++) a[i]=i,update(i,1);
	for(long long i=m+1;i<=m+n-1;i++) a[i]=(i-m+1)*m,update(i,1);
	for(long long i=1;i<=q;i++)
	{
		l=1,r=N2*4;pos=n+m-1+i;
		while(l<=r)
		{
            mid=(l+r)/2;
			if(query(mid)>=y[i]) Y=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",a[Y]);
		update(Y,-1);update(pos,1);a[pos]=a[Y];a[Y]=0;
	}
}

1-20 动态开点线段树

经过动态开点，可以节省一些空间，来足以通过本题。

我们要开 \(q+1\) 棵线段树：为每个询问开一个（好理解的话是每行），为最后一列开一个。

线段树中，只有叶子节点维护 data（题目中人的编号）；各节点维护的信息还有 num（这个节点维护的元素个数）。

  • update 操作：单点修改，修改叶子节点的 data 值。沿途中节点维护元素数加一；在行（或最后一列）的末尾插入即可。
  • query 操作：单点查询，查询线段树中存储的第 rank 个值。沿途中节点维护元素数减一（根据题意，询问完后接着删除）。如果递归进入左子树，仍在左子树查询第 rank 个值；如果进入右子树，则在右子树查询第 (rank \(-\) 左子树元素个数) 个值。

对于每个询问，分两类讨论：

  • 如果 \(y=m\)：

    只在最后一列修改。找到第 \(x\) 个数，输出并放到末尾。

  • 否则：

    先从第 \(x\) 行中找到第 \(y\) 个数，输出并放到最后一列末尾；把最后一列中第 \(x\) 个数放到第 \(x\) 行末尾。

时间复杂度是 \(O(n\log n)\)。本算法可得到 \(100\) 分。

代码

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include<bits/stdc++.h>
using namespace std;
/* 易错点：行列对应关系 
   行    列 
   n     m
   x     y
   i     j
 g[i]   [j]
*/
namespace _FullMarks
{
	/* !!注意!!
	在每次 query 以及 update 操作之后，不要忘记将“地址”赋给 root！
	因为这个，调了将近一个小时（本来可以一遍过） ！ 
	 */
	typedef long long ll;
	const ll N=300000+10,M=1000000000;
	ll cnt=0,n,m,q,root[N],last[N],end,nowAsk,nowAns;
	//对于每个询问，都开一个线段树；为最后一列专门开线段树维护。
	//last 是下一步移到队尾的位置。
	struct SGT
	{
		//线段树中叶子节点 data 是题目所述，人的编号。
		//num 指节点管理的元素个数。
		struct node{int lson,rson,num;ll data; node(){num=data=0;}}t[N*30];
		#define lson t[root].lson
		#define rson t[root].rson
		#define mid ((l+r)/2)
		ll getNum(ll l,ll r)//得到初始管理元素个数。
		{
			/* 管理区间情况（横竖皆可）。
			|----------|---------|--------|---------|
			1          l        r_1     m-1/n      r_2  */
			ll ret=0;
			if(nowAsk==0) ret=min(r,n)-l+1;
			else ret=min(r,m-1)-l+1;
			return max(ret,0ll);//最少管理 0 个元素。
		}
		ll update(ll root,ll l,ll r,ll pos,ll data)
		{
			if(root==0)
			{
				//刚刚开辟的节点，其管理元素分布必定连续。 
				root=++cnt;
				t[root].num+=getNum(l,r); 
			}
			t[root].num++;//根据题意，更新后维护元素个数加一。 
			//并且，update 的位置一定大于 m-1 或 n，这是 getNum 函数覆盖不到的。 
			if(l==r)
			{
				t[root].data=data;
				return root;
			}
			if(pos<=mid) lson=update(lson,l,mid,pos,data);
			else rson=update(rson,mid+1,r,pos,data);
			return root;
		}
		ll query(ll root,ll l,ll r,ll rank)//rank 是指查询数列第几个。
		{
			if(root==0)
			{
				//虽然有些点未创建，但根据题意，
				//仍然不能返回，因为初始返回值可以计算。 
				root=++cnt;
				t[root].num+=getNum(l,r);
				if(l==r)//这个点刚被创建，直接计算值。
				{
					if(nowAsk==0) t[root].data=l*m;
					else t[root].data=nowAsk*m-m+l;
				}
			}
			t[root].num--;//根据题意，查询后直接删除，维护数减一。 
			if(l==r)
			{
				nowAns=t[root].data;//使用它来承载答案。
				return root;//由于 query 函数可能创建节点，所以与 update 类似。 
			}
			ll Lnum;
			if(lson==0) Lnum=getNum(l,mid);//为空就现算。
			else Lnum=t[lson].num;
			if(rank<=Lnum) lson=query(lson,l,mid,rank);
			else rson=query(rson,mid+1,r,rank-Lnum);
			return root; 
		}
	}Tree;
	void yzmain()
	{
		ll x,y;
		scanf("%lld%lld%lld",&n,&m,&q);
		end=max(m,n)+q+10;
		memset(last,0,sizeof(last));
		for(int i=1;i<=q;i++)
		{
			scanf("%lld%lld",&x,&y);
			if(y==m)//直接维护最后一列 
			{
				nowAsk=0;
				root[nowAsk]=Tree.query(root[nowAsk],1,end,x);
				printf("%lld\n",nowAns);last[nowAsk]++;
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+n,nowAns);
			}
			else
			{
				nowAsk=x;//先查询行。
				root[nowAsk]=Tree.query(root[nowAsk],1,end,y);
				printf("%lld\n",nowAns);
				nowAsk=0;last[nowAsk]++;//再塞到最后一列。
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+n,nowAns);
				root[nowAsk]=Tree.query(root[nowAsk],1,end,x);//再把最后一列属于那一行的摘出来。
				nowAsk=x;last[nowAsk]++;//最后塞到那一行。 
				root[nowAsk]=Tree.update(root[nowAsk],1,end,last[nowAsk]+m-1,nowAns);
			}
		}
		return;
	}
}
namespace _yz
{
	const long long N1=1000+10,N2=300000+10,Q1=500+10,N3=50000+10,Q2=300000+10;
	long long n,m,q;//基本变量定义
	long long g[N1][N1];//solve1 2 共用 
	long long a[N2*4],t[N2*4];//solve4 使用 
	long long bx[Q1],fx[N3],ax[Q1];//solve2 3 共用 
	long long x[Q2],y[Q2];//solve2 3 共用，判断特殊点 
	//long long by[Q1],fy[N3],ay[Q1]; //solve2 错误做法 
	long long G[Q1][N3],L[N3];//solve3 使用
	
	long long lb(long long x){return x&-x;}
	long long query(long long x){long long ret=0;while(x>=1)ret+=t[x],x-=lb(x);return ret;}
	void update(long long x,long long y){while(x<=N2*4)t[x]+=y,x+=lb(x);}//solve4 使用 
	void solve1()
	{
		long long x,y;
		for(long long i=1;i<=n;i++)
			for(long long j=1;j<=m;j++)
				g[i][j]=i*m-m+j;
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",g[x][y]);
			for(long long j=y;j<=m-1;j++) swap(g[x][j],g[x][j+1]);
			for(long long j=x;j<=n-1;j++) swap(g[j][m],g[j+1][m]);
		}
	}
	void solve2()//错误做法 
	{
		/*//离散化后结构：网格形 
		long long px=0,py=0;//离散化之后的矩阵的 m n 
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",x+i,y+i);//Query 
			bx[i]=x[i];by[i]=y[i];//b 数组作为 tmp 
		}
		sort(bx+1,bx+1+q);sort(by+1,by+1+q);//Begin of 离散化 
		for(long long i=1;i<=q;i++)
		{
			if(bx[i-1]!=bx[i]) px++;
			if(by[i-1]!=by[i]) py++;
			fx[bx[i]]=px;fy[by[i]]=py;//f 数组用来根据原数找到相对位置 
			ax[px]=bx[i];ay[py]=by[i];//a 数组用来根据相对位置还原原数 
		}
		if(ay[py]!=m) by[++py]=m,fy[m]=py,ay[py]=m; 
		//End of 离散化 
		for(long long i=1;i<=px;i++)
			for(long long j=1;j<=py;j++)
				g[i][j]=ax[i]*m-m+ay[j];//g 数组下标是相对位置 
		for(long long i=1;i<=q;i++)
		{
			printf("%lld\n",g[fx[x[i]]][fy[y[i]]]);
			for(long long j=fy[y[i]];j<=py-1;j++) swap(g[fx[x[i]]][j],g[fx[x[i]]][j+1]);
			for(long long j=fx[x[i]];j<=px-1;j++) swap(g[j][py],g[j+1][py]);
		}*/
	}
	void solve3()
	{
		/* 离散化后结构：
		    -------------- |
		                   |
			-------------- |
			-------------- |
		*/ 
		long long px=0;//离散化之后的行数 
		for(long long i=1;i<=q;i++)
		{
			scanf("%lld%lld",x+i,y+i);//Query 
			bx[i]=x[i];//b 数组作为 tmp 
		}
		sort(bx+1,bx+1+q);//Begin of 离散化 
		for(long long i=1;i<=q;i++)
		{
			if(bx[i-1]!=bx[i]) px++;
			fx[bx[i]]=px;//f 数组用来根据原数找到相对位置 
			ax[px]=bx[i];//a 数组用来根据相对位置还原原数 
		}
		for(long long i=1;i<=px;i++)
			for(long long j=1;j<=m-1;j++)
				G[i][j]=ax[i]*m-m+j;//G 数组下标是相对位置 
		for(long long i=1;i<=n;i++) L[i]=i*m;//L 数组是最后一列 
		for(long long i=1;i<=q;i++)
		{
			if(y[i]!=m) printf("%lld\n",G[fx[x[i]]][y[i]]);
			else printf("%lld\n",L[x[i]]);
			for(long long j=y[i];j<=m-2;j++) swap(G[fx[x[i]]][j],G[fx[x[i]]][j+1]);
			swap(G[fx[x[i]]][m-1],L[x[i]]);
			for(long long j=x[i];j<=n-1;j++) swap(L[j],L[j+1]);
		}
	}
	void solve4()
	{
		long long l,r,mid,Y,pos;
		for(long long i=1;i<=m;i++) a[i]=i,update(i,1);
		for(long long i=m+1;i<=m+n-1;i++) a[i]=(i-m+1)*m,update(i,1);
		for(long long i=1;i<=q;i++)
		{
			l=1,r=N2*4;pos=n+m-1+i;
			while(l<=r)
			{
                mid=(l+r)/2;
				if(query(mid)>=y[i]) Y=mid,r=mid-1;
				else l=mid+1;
			}
			printf("%lld\n",a[Y]);
			update(Y,-1);update(pos,1);a[pos]=a[Y];a[Y]=0;
		}
	}
	void yzmain()
	{
		long long cnt=0;
		scanf("%lld%lld%lld",&n,&m,&q);
		if(n<=1000&&m<=1000&&q<=500) solve1();
		else if(n<=50000&&m<=50000&&q<=500) solve3();
		else{
			for(long long i=1;i<=q;i++)
			{
				scanf("%lld%lld",x+i,y+i);
				if(x[i]==1) cnt++;
			}
			if(cnt==q) solve4();
			else printf("zzy AK IOI!");//zzy 这个大佬非常强！
		}
   		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_FullMarks::yzmain();
	return 0;
}